package me.algo.n;

/**
 * @author guozheng
 * @date 2024/4/29
 */
public class N1 {
    public static void main(String[] args) {
        System.out.println(fib1(45));
        System.out.println(fib(45));
    }

    public static int fib1(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }


    static public int fib(int n) {
        int n0 = 0;
        int n1 = 1;
        if (n == 0) {
            return n0;
        }
        if (n == 1) {
            return n1;
        }
        int md = 1000000007;
        int x1 = n0;
        int x2 = n1;
        for (int i = 0; i < n - 1; i++) {
            int x3 = (x1 + x2) % md;
            x1 = x2;
            x2 = x3;
        }
        return x2;
    }

}
